package ustc.xiaoyang.lingchashan.doublepointer;

import java.util.Arrays;

/**
 * 16.最接近的三数之和 medium
 */
public class ThreeSumClosest16 {
    public int threeSumClosest(int[] nums,int target){
        Arrays.sort(nums);
        int res = 0;
        int diff = 0x3fffffff;
        for (int i = 0; i < nums.length-2; i++) {
            if(i>0 && nums[i] == nums[i-1]) continue;
            int l = i + 1;
            int r = nums.length - 1;
            //优化1
            int s1 = nums[i]+nums[i+1]+nums[i+2];
            if(s1 > target){
                if(s1 - target < diff)
                    res = s1;
                break;
            }
            //优化2
            int s2 = nums[i]+nums[nums.length-1]+nums[nums.length-2];
            if(s2 < target) {
                if(target - s2 <diff) {
                    res = s2;
                    diff = target - s2;
                }
                continue;
            }
            while(l<r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == target){
                    return target;
                }else if(sum < target){
                    if(Math.abs(sum - target) < diff){
                        diff = Math.abs(sum - target);
                        res = sum;
                    }
                    l++;
                }else{
                    if(Math.abs(sum - target) < diff){
                        diff = Math.abs(sum - target);
                        res = sum;
                    }
                    r--;
                }
            }
        }

        return res;

    }
}
